#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode
{
    int val;
    struct ListNode* next;
}ListNode;
     //链表分割
ListNode* partition(ListNode* pHead, int x)
{
    ListNode* list1 = NULL, * tail1 = NULL, * list2 = NULL, * tail2 = NULL;
    while (pHead != NULL)
    {
        if (pHead->val < x)
        {
            if (list1 == NULL)
            {
                tail1 = list1 = pHead;
            }
            else
            {
                tail1->next = pHead;
                tail1 = tail1->next;
            }
        }
        else
        {
            if (list2 == NULL)
            {
                tail2 = list2 = pHead;
            }
            else
            {
                tail2->next = pHead;
                tail2 = tail2->next;
            }
        }
        pHead = pHead->next;

    }
    if (list1 == NULL)
    {
        return list2;
    }
    else
    {
        if (list2 != NULL)
        {
            tail1->next = list2;
            tail2->next = NULL;
        }

        return list1;
    }
}

ListNode* partition(ListNode* pHead, int x)
{
    ListNode* list1, * tail1 , * list2 , * tail2 ;
    list1 = tail1 = (ListNode*)malloc(sizeof(ListNode));
    list2 = tail2 = (ListNode*)malloc(sizeof(ListNode));
    tail1->next = NULL;
    tail2->next = NULL;

    while (pHead != NULL)
    {
        if (pHead->val < x)
        {
                tail1->next = pHead;
                tail1 = pHead;
        }
        else
        {
                tail2->next = pHead;
                tail2 = pHead;
        }
        pHead = pHead->next;

    }
        tail1->next = list2->next;
        tail2->next = NULL;
        ListNode* temp = list1->next;
        free(list1);
        free(list2);
        return temp;
}


void SListPrint(struct ListNode* plist)
{
    struct ListNode* current = plist;
    while (current != NULL)
    {
        printf("%d->", current->val);
        current = current->next;
    }
    printf("NULL\n");
}



  //相交链表
     //第一种：暴力求解
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    if (headA==NULL || headB ==NULL)
    {
        return NULL;
    }
    struct ListNode* cur1 = headA;
    struct ListNode* cur2 = headB;
    while (cur2 != NULL)
    {
        cur1 = headA;
        while (cur1 != NULL)
        {
            if (cur1->next == cur2->next)
            {
                if (cur1->next == NULL)
                {
                    return cur1;
                }
                else
                {
                    return cur1->next;
                }
            }
            else
            {
                cur1 = cur1->next;
            }
        }
        cur2 = cur2->next;
    }
    return NULL;
}

     //第二种（效率高）
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    struct ListNode* curA = headA, * curB = headB;
    int count1 = 0, count2 = 0;
    while (curA->next != NULL)
    {
        count1++;
        curA = curA->next;
    }
    while (curB->next != NULL)
    {
        count2++;
        curB = curB->next;
    }
    int gap = abs(count1 - count2);
    struct ListNode* longlist = headA;
    struct ListNode* shortlist = headB;
    if (count1 < count2)
    {
        longlist = headB;
        shortlist = headA;
    }
    if (curB == curA)
    {
        while (gap--)
        {
            longlist = longlist->next;
        }
        while (longlist != shortlist)
        {
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
        return longlist;
            
    }
    else
    {
        return NULL;
    }
}

int main()
{
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));

    struct ListNode* m1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* m2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* m3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    n1->val = 4;
    n2->val = 1;

    m1->val = 5;
    m2->val = 6;
    m3->val = 1;

    n3->val = 8;
    n4->val = 4;
    n5->val = 5;

    n1->next = n2;
    n2->next = n3;

    m1->next = m2;
    m2->next = m3;
    m3->next = n3;

    n3->next = n4;
    n4->next = n5;
    n5->next = NULL;
    SListPrint(n1);
    SListPrint(m1);
    struct ListNode* Rhead = NULL;
    Rhead = getIntersectionNode(n1, m1);
    SListPrint(Rhead);

    return 0;
}

     //判断链表回文结构
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast, * slow;
    fast = slow = head;
    while (fast != NULL)
    {
        fast = fast->next;
        if (fast != NULL)
        {
            fast = fast->next;
        }
        else
        {
            return slow;
        }
        slow = slow->next;
    }
    return slow;
}

struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL)
        return NULL;
    else if (head->next == NULL)
        return head;
    else
    {
        struct ListNode* n1, * n2, * n3;
        n1 = NULL;
        n2 = head;
        n3 = head->next;
        while (n2 != NULL)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3 != NULL)
            {
                n3 = n3->next;
            }
        }
        return n1;
    }

}

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A)
    {
        // write code here
        // 找到中间节点
        struct ListNode* mid = middleNode(A);
        // 逆置中间节点以后的节点
        struct ListNode* rHead = reverseList(mid);
        // 判断是否回文
        struct ListNode* curA = A;
        struct ListNode* curRhead = rHead;
        while (curA && curRhead)
        {
            if (curA->val != curRhead->val)
                return false;
            else
            {
                curA = curA->next;
                curRhead = curRhead->next;
            }
        }
        return true;
    }
};


     //寻找环的入口点

struct ListNode* detectCycle(struct ListNode* head)
{
    // 找到相遇点
    struct ListNode* fast, * slow;
    fast = slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            return fast;
        }
    }

    // 断开为两个链表
    struct ListNode* cur1, *cur2;
    cur1 = fast->next;
    cur2 = head;

    // 找到两个链表的交点
    /*struct ListNode* move1, * move2;
    int count1 = 0, count2 = 0;
    move1 = cur1;
    move2 = cur2;
    while (move1)
    {
        count1++;
        move1 = move1->next;
    }
    while (move2)
    {
        count2++;
        move2 = move2->next;
    }
    int gap = abs(count1 - count2);
    if (count1 > count2)
    {
        while (gap--)
        {
            cur1 = cur1->next;
        }
    }
    else
    {
        while (gap--)
        {
            cur2 = cur2->next;
        }
    }
    while (cur2 != cur1)
    {
        cur1 = cur1->next;
        cur2 = cur2->next;
    }

    return cur1;*/



}


struct ListNode* getmeetnode(struct ListNode* head)
{
    struct ListNode* fast, * slow;
    fast = slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            return fast;
        }
    }
    return NULL;
}
struct ListNode* detectCycle(struct ListNode* head)
{
    // 找到相遇点

    struct ListNode* meetnode = getmeetnode(head);
    if (meetnode == NULL)
    {
        return NULL;
    }
    // 断开为两个链表
    struct ListNode* cur1, * cur2;
    cur1 = meetnode->next;
    meetnode->next = NULL;
    cur2 = head;

    // 找到两个链表的交点
    struct ListNode* IntersectionNode = getIntersectionNode(cur1, cur2);
    return IntersectionNode;

}

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    if (headA==NULL && headB==NULL)
    {
        return NULL;
    }
    struct ListNode* curA = headA, * curB = headB;
    int count1 = 0, count2 = 0;
    while (curA->next != NULL)
    {
        count1++;
        curA = curA->next;
    }
    while (curB->next != NULL)
    {
        count2++;
        curB = curB->next;
    }
    int gap = abs(count1 - count2);
    struct ListNode* longlist = headA;
    struct ListNode* shortlist = headB;
    if (count1 < count2)
    {
        longlist = headB;
        shortlist = headA;
    }
    if (curB == curA)
    {
        while (gap--)
        {
            longlist = longlist->next;
        }
        while (longlist != shortlist)
        {
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
        return longlist;

    }
    else
    {
        return NULL;
    }
}

struct ListNode* getmeetnode(struct ListNode* head)
{
    struct ListNode* fast, * slow;
    fast = slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            return fast;
        }
    }
    return NULL;
}
struct ListNode* detectCycle(struct ListNode* head)
{
     //找到相遇点

    struct ListNode* meetnode = getmeetnode(head);
    if (meetnode == NULL)
    {
        return NULL;
    }
     //断开为两个链表
    struct ListNode* cur1, * cur2;
    cur1 = meetnode->next;
    meetnode->next = NULL;
    cur2 = head;

     //找到两个链表的交点
    struct ListNode* IntersectionNode = getIntersectionNode(cur1, cur2);
    return IntersectionNode;

}


int main()
{
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));

    /*struct ListNode* m1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* m2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* m3 = (struct ListNode*)malloc(sizeof(struct ListNode));*/
    n1->val = 3;
    n2->val = 2;

  /*  m1->val = 5;
    m2->val = 6;
    m3->val = 1;*/

    n3->val = 0;
    n4->val = -4;
    n5->val = 5;

    n1->next = n2;
    n2->next = n3;

    n3->next = n4;
    n4->next = n2;
    n5->next = n2;

    struct ListNode* retnode = detectCycle(n1);

    SListPrint(n1);

    struct ListNode* Rhead = NULL;
    Rhead = getIntersectionNode(n1, m1);
    SListPrint(retnode);

    return 0;
}